class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.column = [[False] * 9 for _ in range(9)]   # 存储列数据
        self.row = [[False] * 9 for _ in range(9)]      # 存储行数据
        self.region = [[[False] * 9 for _ in range(3)] for _ in range(3)] # 存储区数据
        self.valid = False  # 标记是否已找到解
        self.spaces = []  # 存储空格的位置

        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    self.spaces.append((i, j))
                else:
                    a = int(board[i][j]) - 1  # 转换为0-8的索引
                    self.row[i][a] = True
                    self.column[j][a] = True
                    x = i // 3
                    y = j // 3
                    self.region[x][y][a] = True

        def go(pos):
            if pos == len(self.spaces):  # 所有空格都已填充
                self.valid = True
                return
            i, j = self.spaces[pos]
            for a in range(9):  # 尝试数字1-9 (索引0-8)
                x = i // 3
                y = j // 3
                if not self.row[i][a] and not self.column[j][a] and not self.region[x][y][a]:
                    self.row[i][a] = self.column[j][a] = self.region[x][y][a] = True
                    board[i][j] = str(a + 1)
                    go(pos + 1)
                    if not self.valid:
                        self.row[i][a] = self.column[j][a] = self.region[x][y][a] = False
                    else:
                        return
        go(0)